Analyzing change in spatial data by utilizing polygon models.

Correspondence Clustering An Approach to Cluster Multiple Related Spatial Datasets.

A Framework for Multi%2DObjective Clustering and Its Application to Co%2DLocation Mining.
Abstract. The goal of multi-objective clustering (MOC) is to decompose a dataset into similar groups maximizing multiple objectives in parallel. In this paper, we provide a methodology, architecture and algorithms that, based on a large set of objectives, derive interesting clusters regarding two or more of those objectives. The proposed architecture relies on clustering algorithms that support plug-in fitness functions and on multi-run clustering in which clustering algorithms are run multiple times maximizing different subsets of objectives that are captured in compound fitness functions. MOC provides search engine type capabilities to users, enabling them to query a large set of clusters with respect to different objectives and thresholds. We evaluate the proposed MOC framework in a case study that centers on spatial co-location mining; the goal is to identify regions in which high levels of Arsenic concentrations are co-located with high concentrations of other chemicals in the Texas water supply. Keywords: Multi-objective clustering, knowledge discovery, spatial data mining, co-location mining, clustering with plug-in fitness functions. 1
An architecture and algorithms for multi%2Drun clustering.
Abstract—This paper addresses two main challenges for clustering which require extensive human effort: selecting appropriate parameters for an arbitrary clustering algorithm and identifying alternative clusters. We propose an architecture and a concrete system MR-CLEVER for multi-run clustering that integrates active learning with clustering algorithms. The key hypothesis of this work is that better clustering results can be obtained by combining clusters that originate from multiple runs of clustering algorithms. By defining states that represent parameter settings of a clustering algorithm, the proposed architecture actively learns a state utility function. The utility of a parameter setting is assessed based on clustering run-time, quality and novelty of the obtained clusters. Furthermore, the utility function plays an important role in guiding the clustering algorithm to seek novel solutions. Cluster novelty measures are introduced for this purpose. Finally, we also contribute a cluster summarization algorithm that assembles a final clustering as a combination of high-quality clusters originating from multiple runs. Merits of our proposed system are that it is generic and therefore can be used in conjunction with different clustering algorithms, and it reduces human effort for selecting the parameters, for comparing clustering results and for assembling clustering results. We evaluate the proposed system in conjunction with a representative based clustering algorithm namely CLEVER for a challenging data mining task involving an earthquake dataset. The obtained results demonstrate that, in comparison to the best single-run clustering, multi-run clustering discovers solutions of higher quality. C I.
REG%5E2 a regional regression framework for geo%2Dreferenced datasets.
Traditional regression analysis derives global relationships between variables and neglects spatial variations in variables. Hence they lack the ability to systematically discover regional relationships and to build better models that use this regional knowledge to obtain higher prediction accuracies. Since most relationships in spatial datasets are regional, there is a great need for regional regression methods that derive regional regression functions that reflect different spatial characteristics of different regions. This paper proposes a novel regional regression framework that first discovers interesting regions showing strong regional relationships between the dependent and the independent variables, and then builds a prediction model with a regional regression function associated with each region. Interesting regions are identified by running a representative-based clustering algorithm that maximizes an externally plugged in fitness function. In this work, we propose two fitness functions: an R-squared based fitness function and an AIC-based fitness function to handle overfitting better. We evaluate our framework in two case studies; (1) identifying causes of arsenic contamination in Texas water wells and (2) Boston Housing dataset determining spatially varying effects of house properties on house prices. We demonstrated that our framework effectively identifies interesting regions and builds better prediction systems that rely on regional models.
Regional Pattern Discovery in Geo%2Dreferenced Datasets Using PCA.
Abstract. Existing data mining techniques mostly focus on finding global patterns and lack the ability to systematically discover regional patterns. Most relationships in spatial datasets are regional; therefore there is a great need to extract regional knowledge from spatial datasets. This paper proposes a novel framework to discover interesting regions characterized by “strong regional correlation relationships ” between attributes, and methods to analyze differences and similarities between regions. The framework employs a twophase approach: it first discovers regions by employing clustering algorithms that maximize a PCA-based fitness function and then applies post processing techniques to explain underlying regional structures and correlation patterns. Additionally, a new similarity measure that assesses the structural similarity of regions based on correlation sets is introduced. We evaluate our framework in a case study which centers on finding correlations between arsenic pollution and other factors in water wells and demonstrate that our framework effectively identifies regional correlation patterns.
Change Analysis in Spatial Data by Combining Contouring Algorithms with Supervised Density Functions.
Abstract Detecting changes in spatial datasets is important for many fields. In this paper, we introduce a methodology for change analysis in spatial datasets that combines contouring algorithms with supervised density estimation techniques. The methodology allows users to define their own criteria for features of interest and to identify changes in those features between two datasets. Change analysis is performed by comparing interesting regions that have been derived using contour clustering. A novel clustering algorithm called DCONTOUR is introduced for this purpose that computes contour polygons that describe the boundary of a supervised density function at a given density threshold. Relationships between old and new data are analyzed relying on polygon operations. We evaluate our methodology in case studies that analyze changes in earthquake patterns.
Change analysis in spatial datasets by interestingness comparison.
ACM SIGSPATIAL addresses issues related to the acquisition, management, and processing of spatially-related information with a focus on algorithmic, geometric, and visual considerations. The scope includes, but is not limited to, geographic information systems. Current ACM SIGSPATIAL officers are:
Finding regional co%2Dlocation patterns for sets of continuous variables in spatial datasets.

Discovering controlling factors of geospatial variables.
Efficient means of determining factors controlling spatial distribution of an environmental class variable are of significant interest in Earth science. In this paper, we present a method for automated discovery of controlling factors by mining for emerging patterns in a database constructed from the fusion of several explanatory datasets. We introduce a new definition of pattern support to account for spatial character of the data and systematically evaluate the effectiveness of our technique using a real-world application pertaining to density of vegetation cover. Experimental results show that our method can successfully identify controlling factors for the presence of high vegetation cover.
Towards Region Discovery in Spatial Datasets.
Abstract. This paper presents a novel region discovery framework geared towards finding scientifically interesting places in spatial datasets. We view region discovery as a clustering problem in which an externally given fitness function has to be maximized. The framework adapts four representative clustering algorithms, exemplifying prototype-based, gridbased, density-based, and agglomerative clustering algorithms, and then we systematically evaluated the four algorithms in a real-world case study. The task is to find feature-based hotspots where extreme densities of deep ice and shallow ice co-locate on Mars. The results reveal that the density-based algorithm outperforms other algorithms inasmuch as it discovers more regions with higher interestingness, the grid-based algorithm can provide acceptable solutions quickly, while the agglomerative clustering algorithm performs best to identify larger regions of arbitrary shape. Moreover, the results indicate that there are only a few regions on Mars where shallow and deep ground ice co-locate, suggesting that they have been deposited at different geological times.
Distance Function Learning for Supervised Similarity Assessment.

MOSAIC A Proximity Graph Approach for Agglomerative Clustering.
Abstract. Representative-based clustering algorithms are quite popular due to their relative high speed and because of their sound theoretical foundation. On the other hand, the clusters they can obtain are limited to convex shapes and clustering results are also highly sensitive to initializations. In this paper, a novel agglomerative clustering algorithm called MOSAIC is proposed which greedily merges neighboring clusters maximizing a given fitness function. MOSAIC uses Gabriel graphs to determine which clusters are neighboring and approximates non-convex shapes as the unions of small clusters that have been computed using a representative-based clustering algorithm. The experimental results show that this technique leads to clusters of higher quality compared to running a representative clustering algorithm standalone. Given a suitable fitness function, MOSAIC is able to detect arbitrary shape clusters. In addition, MOSAIC is capable of dealing with high dimensional data. Keywords: Post-processing, hybrid clustering, finding clusters of arbitrary shape, agglomerative clustering, using proximity graphs for clustering. 1
On supervised density estimation techniques and their application to spatial data mining.

On Regional Association Rule Scoping.
A special challenge for spatial data mining is that information is not distributed uniformly in spatial data sets. Consequently, the discovery of regional knowledge is of fundamental importance. Unfortunately, regional patterns frequently fail to be discovered due to insufficient global confidence and/or support in traditional association rule mining. Regional association rules, by definition, only hold in a subspace but not in the global space. One novel challenge is how to evaluate the impact of regional association rules. This paper centers on regional association rule scoping. We introduce a reward-based region discovery framework that employs clustering to find places where regional association rules are valid. We evaluate our approach in a real-world case study to discover arsenic risk zones in the Texas water supply. The experimental results are validated by domain experts and compared with published results on arsenic contamination. 1


Discovery of Interesting Regions in Spatial Data Sets Using Supervised Clustering.
Abstract. The discovery of interesting regions in spatial datasets is an important data mining task. In particular, we are interested in identifying disjoint, contiguous regions that are unusual with respect to the distribution of a given class; i.e. a region that contains an unusually low or high number of instances of a particular class. This paper centers on the discussion of techniques, methodologies, and algorithms to discover such regions. A measure of interestingness and a supervised clustering framework are introduced for this purpose. Moreover, three supervised clustering algorithms are proposed in the paper: an agglomerative hierarchical supervised clustering named SCAH, an agglomerative, grid-based clustering method named SCHG, and lastly an algorithm named SCMRG which searches a multi-resolution grid structure top down for interesting regions. Finally, experimental results of applying the proposed framework and algorithms to the problem of identifying hotspots in spatial datasets are discussed. 1
Using clustering to learn distance functions for supervised similarity assessment.

Adaptive Clustering Obtaining Better Clusters Using Feedback and Past Experience.
Adaptive clustering uses external feedback to improve cluster quality; past experience serves to speed up execution time. An adaptive clustering environment is proposed that uses Q-learning to learn the reward values of successive data clusterings. Adaptive clustering supports the reuse of clusterings by memorizing what worked well in the past. It has the capability of exploring multiple paths in parallel when searching for good clusters. In a case study, we apply adaptive clustering to instance-based learning relying on a distance function modification approach. A distance function adaptation scheme that uses external feedback is proposed and compared with other distance function learning approaches. Experimental results indicate that the use of adaptive clustering leads to significant improvements of instance-based learning techniques, such as k-nearest neighbor classifiers. Moreover, as a by-product a new instance-based learning technique is introduced that classifies examples by solely using cluster representatives; this technique shows high promise in our experimental evaluation. 1.
Content%2DBased Image Retrieval through a Multi%2DAgent Meta%2DLearning Framework.
The objective of a general-purpose content-based image retrieval system is to find images in a database that match an external measure of relevance. Since users follow different and inconsistent relevance measures, processing queries in a task-specific manner has shown to be an effective approach. Viewing specialized image retrieval algorithms as agents, we propose a general-purpose image retrieval system that uses a new multi-agent meta-learning framework. The framework adapts a distance function defined over both image distance weights and image queries to identify clusters of algorithms that produce similar solutions to similar problems. Experiments compare our approach with a traditional information retrieval algorithm; results show that our framework provides better average relevance scores. 1.
Using Supervised Clustering to Enhance Classifiers.
Abstract. This paper centers on a novel data mining technique we term supervised clustering. Unlike traditional clustering, supervised clustering is applied to classified examples and has the goal of identifying class-uniform clusters that have a high probability density. This paper focuses on how data mining techniques in general, and classification techniques in particular, can benefit from knowledge obtained through supervised clustering. We discuss how better nearest neighbor classifiers can be constructed with the knowledge generated by supervised clustering, and provide experimental evidence that they are more efficient and more accurate than a traditional 1-nearest-neighbor classifier. Finally, we demonstrate how supervised clustering can be used to enhance simple classifiers. 1
Using Clustering to Learn Distance Functions for Supervised Similarity Assessment.

K%2Dmedoid%2Dstyle Clustering Algorithms for Supervised Summary Generation.
This paper centers on the discussion of k-medoid-style clustering algorithms for supervised summary generation. This task requires clustering techniques that identify class-uniform clusters. This paper investigates such a novel clustering technique we term supervised clustering. Our work focuses on the generalization of k-medoid-style clustering algorithms. We investigate two supervised clustering algorithms: SRIDHCR (Single Representative Insertion/Deletion Hill Climbing with Restart) and SPAM, a variation of PAM. The solution quality and run time of these two algorithms as well as the traditional clustering algorithm PAM are evaluated using a benchmark consisting of four data sets. Experiments show that supervised clustering algorithms enhance class purity by 7 % to 19 % over the traditional clustering algorithm PAM, and that SRIDHCR finds better solutions than SPAM. Key Words: supervised summary generation, clustering classified examples, k-medoid clustering algorithms, data mining. 1.
A Systematic Database Summary Generation Using the Distributed Query Discovery System.

Using Representative%2DBased Clustering for Nearest Neighbor Dataset Editing.
The goal of dataset editing in instance-based learning is to remove objects from a training set in order to increase the accuracy of a classifier. For example, Wilson editing removes training examples that are misclassified by a nearest neighbor classifier so as to smooth the shape of the resulting decision boundaries. This paper revolves around the use of representative-based clustering algorithms for nearest neighbor dataset editing. We term this approach supervised clustering editing. The main idea is to replace a dataset by a set of cluster prototypes. A novel clustering approach called supervised clustering is introduced for this purpose. Our empirical evaluation using eight UCI datasets shows that both Wilson and supervised clustering editing improve accuracy on more than 50 % of the datasets tested. However, supervised clustering editing achieves four times higher compression rates than Wilson editing; moreover, it obtains significantly high accuracies for three of the eight datasets tested.
Supervised Clustering %2D Algorithms and Benefits.
This paper centers on a novel data mining technique we term supervised clustering. Unlike traditional clustering, supervised clustering assumes that the examples are classified and has the goal of identifying class-uniform clusters that have high probability densities. Four representative–based algorithms for supervised clustering are introduced: a greedy algorithm with random restart, named SRIDHCR, that seeks for solutions by inserting and removing single objects from the current solution, SPAM (a variation of the clustering algorithm PAM), an evolutionary computing algorithm named SCEC, and a fast medoid-based top-down splitting algorithm, named TDS. The four algorithms were evaluated using a benchmark consisting of four UCI machine learning data sets. In general, it seems that “greedy ” algorithms, such as SPAM, SRIDHCR, and TDS, do not perform particularly well for supervised clustering and seem to terminate prematurely too often. We also briefly describe the applications of supervised clustering. 1.
Class Decomposition via Clustering A New Framework for Low%2DVariance Classifiers.
In this paper we propose a pre-processing step to classification that applies a clustering algorithm to the training set to discover local patterns in the attribute or input space. We demonstrate how this knowledge can be exploited to enhance the predictive accuracy of simple classifiers. Our focus is mainly on classifiers characterized by high bias but low variance (e.g., linear classifiers); these classifiers experience difficulty in delineating class boundaries over the input space when a class distributes in complex ways. Decomposing classes into clusters makes the new class distribution easier to approximate and provides a viable way to reduce bias while limiting the growth in variance. Experimental results on real-world domains show an advantage in predictive accuracy when clustering is used as a preprocessing step to classification. 1
Fast Decision Tree Learning Algorithms for Microarray Data Collections.

A heuristic search based factoring tool.

Emperor Cheap Legal Secure Cryptography for the Web.

Supporting Polyploidy in Genetic Algorithms Using Dominance Vectors.

Using Offset Invariant Crossover as a Tool for Discovering Cycle Lengths of a Periodic Function.

Supporting Polyploidy in Genetic Algorithms Using Dominance Vectors.

Using Recurrent Selection to Improve GA Performance.

Using Recurrent Selection to Improve GA Performance.


Deriving Queries from Results Using Genetic Programming.


Enhancing Diversity for a Genetic Algorithm Learning Environment for Classfication Tasks.

An Adaptive Browsing System Based on Rules for Object%2DOriented Databases.

Evaluation and Enhancement of Bayesian Rule%2DSets in a Genetic Algorithm Learning Environment for Classification Tasks.
The paper describes an inductive learning environment called DELVAUX for classification tasks that learns PROSPECTOR-style, Bayesian rules from sets of examples. A genetic algorithm approach is used for learning Bayesian rule-sets, in which a population consists of sets of rule-sets that generate offsprings through the exchange of rules, permitting fitter rule-sets to produce offsprings with a higher probability. Reward and punishment mechanisms are introduced that evaluate the performance of a Bayesian rule within a rule-set. For this purpose, fuzzy techniques that evaluate the &#034;goodness&#034; of a rule within a rule-set are provided. A new mutation operator is introduced that uses this evaluation information, which replaces bad rules with higher probabilities than good rules, when a mutation occurs. Empirical results that evaluate the presented reward-punishment techniques are presented. Finally, we compare our learning environment that learns fuzzy rules that rely on decision making by evidence combination with classical classifier systems that rely on non-fuzzy, data-driven rules and the bucket brigade algorithm.  Key words: Evolutionary computation, learning and adaptive systems; genetic algorithms, classifier systems, Bayesian rule-based systems, inductive learning, approximate reasoning, knowledge discovery, bucket brigade algorithm, automatic rule debugging.  1  2 1 
Learning Bayesian Classification Rules through Genetic Algorithms.

Expression and Enforcement of Dynamic Integrity Constraints.

Integrating Sets%2C Rules%2C and Data in an Object%2DOriented Environment.

Rule%2DBased Consistency Enforcement for Knowledge%2DBased Systems.

Rules in an Extended C  .

Suggesting Causes of Faults in Data%2DDriven Rule%2DBased Systems.

Activation pattern controlled rules Towards an integration of data%2Ddriven and command%2Ddriven programming.

Integrating forward%2Dchaining rules with operations and permanent knowledge bases.

TANGUY Integrating Database%2C Rule%2Dbased and Object%2DOriented Paradigms.

Integrating Variables and Operations into Rule%2DBased Forward Chaining Systems.

A Methodology for the Design and Transformation of Conceptual Schemas.

Toward a Formal Semantics and Inference Rules for Conceptual Data Models.

Integration of Rules into a Knowledge Base Management System.

DALI %2D a Knowledge Base Management System.

Acquisition of Terminological Knowledge Using Database Design Techniques.

From Natural Language Requirements to good Data Base Definitions %2D A Data Base Design Methodology.

Problem Solving by Hyper Planning.

